

// 41.缺失的第一个正数
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        // 将每一个数调整到对应的下标位置
        int n = nums.size();
        for(int i = 0; i < n ; i++)
        {
            while(nums[i] != i + 1 && nums[i] > 0 && nums[i] <= n)   // 换座位
                if(nums[i] == nums[nums[i] - 1]) break;              // 相等不用交换,如果交换可能导致超时,如[1,1]
                else swap(nums[i] , nums[nums[i] - 1]);
        }
        for(int i = 0 ; i < n ; i++)
            if(nums[i] != i + 1) return i + 1;
        return n + 1;
    }
};